#include "stdio.h"
#include "malloc.h"
#define ERROR 0
#define OK 1
#define ElemType int
#define SElemType BitTree
#define Init_length 100
#define Stack_adding 10
#define QElemType BitTree
#define Qlength 100
typedef struct BitNode{
	ElemType data;
	struct BitNode *lchild,*rchild;
}BitNode,*BitTree;

typedef struct {
	QElemType *base;
	int front,rear;
}SqQueue;

typedef struct {
	SElemType *top,*base;
	int stacksize;
}SqStack;
void init_queue(SqQueue *Q){
	Q->base=(QElemType *)malloc(sizeof(QElemType)*Qlength);
	Q->front=Qlength-1;
	Q->rear=Q->front;
}
void en_queue(QElemType t,SqQueue *Q){
	if((Q->front-Q->rear+Qlength)%Qlength>=Qlength-1)
		return;
	else{
		Q->base[Q->rear]=t;
		Q->rear=(Q->rear-1+Qlength)%Qlength;
	}
}
QElemType de_queue(SqQueue *Q){
	QElemType t;
	if(Q->rear==Q->front)
		return NULL;
	else{
		t= Q->base[Q->front];
		Q->front=(Q->front-1+Qlength)%Qlength;
		return t;
	}
}
void init_stack(SqStack *s){
	s->base=(SElemType *)malloc(sizeof(SElemType)*Init_length);
	s->top=s->base;
	s->stacksize=Init_length;
}
void push(SElemType n,SqStack *s){
	if(s->top-s->base>=s->stacksize-1){
		s->base=(SElemType* )realloc(s->base,(s->stacksize+Stack_adding)*sizeof(SElemType));
		s->top=s->base+s->stacksize-1;
	}
	*(s->top)=n;
	s->top++;
}
SElemType pop(SqStack *s){
	return *(--(s->top));
}
BitTree creat(BitTree T,int n){
	int i,t;
	BitNode *p;
	for(i=0;i<n;i++){
		scanf("%d",&t);
		if(i==0){
			if((T=(BitNode *)malloc(sizeof(BitNode)))==0)
						return ERROR;
			T->data=t;
			T->lchild=NULL;
			T->rchild=NULL;
			continue;
		}
		p=T;
		while(1){
			if(t<p->data){
				if(p->lchild!=NULL)
					p=p->lchild;
				else{
					if((p->lchild=(BitNode *)malloc(sizeof(BitNode)))==0)
						return ERROR;
					p=p->lchild;
					p->data=t;
					p->lchild=NULL;
					p->rchild=NULL;
					break;
				}
			}
			else if(t>p->data){
				if(p->rchild!=NULL)
					p=p->rchild;
				else{
					if((p->rchild=(BitNode *)malloc(sizeof(BitNode)))==0)
						return ERROR;
					p=p->rchild;
					p->data=t;
					p->lchild=NULL;
					p->rchild=NULL;
					break;
				}
			}
			else
				break;
		}
	}
	return T;
}
void pre_traverse(BitTree T){
	if(T!=NULL){
		printf("%d ",T->data);
		pre_traverse(T->lchild);
		pre_traverse(T->rchild);
	}
}
void in_traverse(BitTree T){
	if(T!=NULL){
		in_traverse(T->lchild);
		printf("%d ",T->data);
		in_traverse(T->rchild);
	}
}
void post_traverse(BitTree T){
	if(T!=NULL){
		post_traverse(T->lchild);
		post_traverse(T->rchild);
		printf("%d ",T->data);
	}
}
void stack_in_traverse(BitTree T){
	SqStack ss;
	SqStack *s=&ss;
	init_stack(s);
	while(s->top-s->base>0||T!=NULL){
		if(T){
			push (T,s);
			T=T->lchild;
		}
		else{
			T=pop(s);
			printf("%d ",T->data);
			T=T->rchild;
		}
	}
}
int insert(int t,BitTree T){
	BitNode *p;
	p=T;
		while(1){
			if(t<p->data){
				if(p->lchild!=NULL)
					p=p->lchild;
				else{
					if((p->lchild=(BitNode *)malloc(sizeof(BitNode)))==0)
						return ERROR;
					p=p->lchild;
					p->data=t;
					p->lchild=NULL;
					p->rchild=NULL;
					break;
				}
			}
			else if(t>p->data){
				if(p->rchild!=NULL)
					p=p->rchild;
				else{
					if((p->rchild=(BitNode *)malloc(sizeof(BitNode)))==0)
						return ERROR;
					p=p->rchild;
					p->data=t;
					p->lchild=NULL;
					p->rchild=NULL;
					break;
				}
			}
			else
				break;
		}
}
int search(int n,BitTree T){
	BitNode *p=T;
	while(1){
		if(n==p->data)
			return OK;
		else if(n<p->data){
			if(p->lchild==NULL)
				return ERROR;
			else
				p=p->lchild;
		}
		else {
			if(p->rchild==NULL)
				return ERROR;
			else
				p=p->rchild;
		}
	}
}
void level_traverse(BitTree T){
	SqQueue QQ;
	SqQueue *q=&QQ;
	init_queue(q);
	if(T!=NULL);
		en_queue(T,q);
	while(q->rear!=q->front){
		if(q->base[q->front]->lchild!=NULL)
			en_queue(q->base[q->front]->lchild,q);
		if(q->base[q->front]->rchild!=NULL)
			en_queue(q->base[q->front]->rchild,q);
			printf("%d ",*de_queue(q));

	}
}
void child_reverse(BitTree T){
	BitNode *t;
	if(T!=NULL){
		t=T->rchild;
		T->rchild=T->lchild;
		T->lchild=t;
		child_reverse(T->lchild);
		child_reverse(T->rchild);
	}
}
int leaves_counter(BitTree T){
	SqStack ss;
	SqStack *s=&ss;
	int count=0;
	init_stack(s);
	while(s->top-s->base>0||T!=NULL){
		if(T){
			push (T,s);
			T=T->lchild;
		}
		else{
			T=pop(s);
			if(T->rchild==NULL&&T->lchild==NULL)
				count++;
			T=T->rchild;
		}
	}
	return count;
}
int depth(BitTree T){
	if(T==NULL)return 0;
	int dl=depth(T->lchild);
	int dr=depth(T->rchild);
	return (dl>dr?dl:dr)+1;
}


int main(){
	int n;
	BitTree T=NULL;
	scanf("%d",&n);
	T=creat(T,n);
	pre_traverse(T);
	printf("\n");
	in_traverse(T);
	printf("\n");
	post_traverse(T);
	printf("\n");
	scanf("%d",&n);
	printf("%d\n",search(n,T));
	scanf("%d",&n);
	printf("%d\n",search(n,T));
	scanf("%d",&n);
	insert(n,T);
	pre_traverse(T);
	printf("\n");
	in_traverse(T);
	printf("\n");
	post_traverse(T);
	printf("\n");
	stack_in_traverse(T);
	printf("\n");
	level_traverse(T);
	printf("\n");
	child_reverse(T);
	pre_traverse(T);
	printf("\n");
	in_traverse(T);
	printf("\n");
	post_traverse(T);
	printf("\n");
	child_reverse(T);
	pre_traverse(T);
	printf("\n");
	in_traverse(T);
	printf("\n");
	post_traverse(T);
	printf("\n");
	printf("%d\n",depth(T));
	printf("%d\n",leaves_counter(T));
	return 0;
}
